import java.util.Arrays;

class Solution {


    /**
     * 搜索插入位置
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    /**
     * x的平方根
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        if(x < 1) return 0;
        int left = 0;
        long right = x;
        while (left < right){
            long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = (int)mid;
            else right = (int)mid -1;
        }

        return left;
    }

    /**
     * 第三大的数
     * @param nums
     * @return
     */
    public static int thirdMax(int[] nums) {
        Arrays.sort(nums);
        if(nums.length <= 2) return nums[nums.length - 1 ];
        int end = nums.length - 2;
        int count = 1;
        while (end >= 0) {
            if (nums[end] != nums[end + 1])
                count++;
            if (count == 3)
                return nums[end];
            end--;
        }
        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(2147483647));
    }
}



